class Solution{
    
public:
    int numTrees(int n) 
    {
        vector<int> num(n + 1, 1);
            
        for (int i = 2; i <= n; ++i) 
        {
            num[i] = 0;
            
            for (int j = 0; j < i; ++j)
            {
                num[i] += (num[j] * num[i-1-j]);
            }
        }
            
        return num[n];
    }
};